HashtableLookup

按输入键在已排序的键表中做二分查找，写出对应字符串指针与命中标记。 算子名虽含 Hashtable，实现为有序表二分查找，要求 key_table 严格升序。

对每个下标 \(i = 0,\ldots,L-1\)，其中 \(L\) 为 input_len：在 key_table[0..num_keys) 上查找 input[i]。

\[\begin{split}\begin{cases} \text{若存在 } j \text{ 使 } \mathrm{key\_table}[j]=\mathrm{input}[i], & \begin{aligned} \mathrm{output\_value}[i] &\leftarrow \mathrm{value\_table}[j] \\ \mathrm{output\_hits}[i] &\leftarrow 1 \end{aligned} \\[6pt] \text{否则}, & \begin{aligned} \mathrm{output\_value}[i] &\leftarrow \mathrm{NULL} \\ \mathrm{output\_hits}[i] &\leftarrow 0 \end{aligned} \end{cases}\end{split}\]

未命中时 output_value[i] 写空指针 NULL，而非空字符串；命中时拷贝的是 value_table 中的字符串指针。

输入：

  • input - 待查键数组地址，元素类型 int32，长度 input_len

  • key_table - 已升序排序的键表地址，元素类型 int32，长度 num_keys

  • value_table - 字符串指针表地址，类型 char **，与 key_table 一一对应

  • num_keys - 键表 / 值表长度

  • input_len - 输入键个数 \(L\)

  • core_mask - 核掩码（仅共享存储版本使用）

输出：

  • output_value - 查找结果指针表，类型 char **，长度 input_len

  • output_hits - 命中标记，类型 unsigned char / uint8_t，长度 input_len；1 命中，0 未命中

支持平台：

FT78NE MT7004

备注

  • FT78NE / MT7004 均为 int32 键，字符串指针值表

  • key_table 必须已按升序排序，否则结果不正确

  • 时间复杂度约为 \(O(L \log N)\)，其中 \(N\) 为 num_keys

共享存储版本:

void i32_hashtable_lookup_s(int *input, int *key_table, char **value_table, int num_keys, char **output_value, unsigned char *output_hits, int input_len, int core_mask)

C调用示例：

 1// MT7004 示例（共享存储多核，DDR 地址）
 2void TestHashtableLookupSMC(int input_len, int core_mask) {
 3    int core_id = get_core_id();
 4    int logic_core_id = GetLogicCoreId(core_mask, core_id);
 5    int core_num = GetCoreNum(core_mask);
 6    int *input = (int *)0x82000000;
 7    int *key_table = (int *)0x82800000;
 8    char **value_table = (char **)0x83000000;
 9    char **output_value = (char **)0x84000000;
10    unsigned char *output_hits = (unsigned char *)0x85000000;
11    int num_keys = input_len / 8;
12    sys_bar(0, core_num);
13    i32_hashtable_lookup_s(input, key_table, value_table, num_keys, output_value, output_hits, input_len, core_mask);
14}
15
16void main() {
17    int core_mask = 0b1111;
18    TestHashtableLookupSMC(256, core_mask);
19}

私有存储版本:

void i32_hashtable_lookup_p(int *input, int *key_table, char **value_table, int num_keys, char **output_value, unsigned char *output_hits, int input_len)

C调用示例：

 1// MT7004 示例（私有存储单核，AM 地址）
 2void TestHashtableLookupAM(int input_len) {
 3    int *input = (int *)0x10010000;
 4    int *key_table = (int *)0x10020000;
 5    char **value_table = (char **)0x10030000;
 6    char **output_value = (char **)0x10040000;
 7    unsigned char *output_hits = (unsigned char *)0x10050000;
 8    int num_keys = input_len / 8;
 9    i32_hashtable_lookup_p(input, key_table, value_table, num_keys, output_value, output_hits, input_len);
10}
11
12void main() {
13    TestHashtableLookupAM(256);
14}